import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=3):
        self.k = k  # 近邻数量
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        """训练模型（存储训练数据）"""
        self.X_train = X
        self.y_train = y

    def predict(self, X_test):
        """对测试集进行预测"""
        predictions = [self._predict(x) for x in X_test]
        return np.array(predictions)

    def _predict(self, x):
        """对单个样本x进行预测"""
        # 1. 计算x与所有训练样本的欧氏距离
        distances = [np.sqrt(np.sum((x - x_train) ** 2)) for x_train in self.X_train]
        # 2. 按距离排序，取前k个索引
        k_indices = np.argsort(distances)[:self.k]
        # 3. 取前k个对应的标签
        k_labels = [self.y_train[i] for i in k_indices]
        # 4. 投票选出现次数最多的标签
        most_common = Counter(k_labels).most_common(1)
        return most_common[0][0]

# 示例：用iris数据集测试
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

knn = KNN(k=5)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

print("预测准确率：", accuracy_score(y_test, y_pred))